/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */

#ifndef _ALBEROBIN_H_
#define _ALBEROBIN_H_

#include <iostream>
using namespace std;

#define NDEBUG
#include <cassert>

#include "nodobin.h"



template <class T>
class Alberobin {
public:
	Alberobin();
	~Alberobin();


	typedef NodoBin<T> * posizione;


	//Operatori
	void creaBinAlbero();
	bool binAlberoVuoto();
	posizione binRadice()               throw (char const *) ;
	posizione padre(posizione)          throw (char const *) ;
	posizione figlioSinistro(posizione) throw (char const *);
	posizione figlioDestro(posizione)   throw (char const *);
	bool sinistroVuoto(posizione)       throw (char const *);
	bool destroVuoto(posizione)         throw (char const *);

	void insBinRadice()        			throw (char const *);
	void insBinRadice( T )				throw (char const *);
	void insBinRadice( Alberobin )		throw (char const *);

	void insFiglioSinistro( posizione ) 			throw (char const *);
	void insFiglioSinistro( posizione, T )			throw (char const *);
	void insFiglioSinistro( posizione, Alberobin )	throw (char const *);

	void insFiglioDestro( posizione )				throw (char const *);
	void insFiglioDestro( posizione, T )			throw (char const *);
	void insFiglioDestro( posizione, Alberobin )	throw (char const *);

	void cancSottoBinAlbero( posizione )throw (char const *);


	T leggiNodo(posizione)              throw (char const *);
	void scriviNodo(T,posizione)		throw (char const *);


	//overloading operatori



	//operatori personalizzati
	void print();
	void print(posizione);

	void visitaPreordine();
	void visitaPostordine();
	void visitaSimmetrica();
	void visitaPreordine(posizione);
	void visitaPostordine(posizione);
	void visitaSimmetrica(posizione);

private:
	posizione radice;
};



/*****************************
 *        DEFINIZIONI        *
 *  dei metodi di Alberobin  *
 *****************************/


template <class T>
Alberobin<T>::Alberobin() {
	creaBinAlbero();
}


template <class T>
Alberobin<T>::~Alberobin() {}


template <class T>
void Alberobin<T>::creaBinAlbero() {
	radice = NULL ;
}



template <class T>
bool Alberobin<T>::binAlberoVuoto() {
	return ( radice == NULL ) ;
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::binRadice()  throw (char const *) {
	if ( ! binAlberoVuoto() )
		return ( radice ) ;
	else
		throw "L'albero è vuoto." ;
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::padre(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( nodo != binRadice() )
			return ( nodo -> getPadre() ) ;
		else
			throw "La radice non ha padre";
	else
		throw "L'albero e' vuoto. Non c'e' radice";
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::figlioSinistro(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() ) {
		posizione left = nodo -> getFiglioSinistro();
		if ( left != NULL )
			return ( left ) ;
		else
			throw "Il nodo non ha il figlio sinistro";
	}
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::figlioDestro(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() ) {
		posizione right = nodo -> getFiglioDestro();
		if ( right != NULL )
			return ( right ) ;
		else
			throw "Il nodo non ha il figlio destro";
	}
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}




template <class T>
bool Alberobin<T>::sinistroVuoto(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() )
		return ( nodo->getFiglioSinistro() == NULL ) ;
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}




template <class T>
bool Alberobin<T>::destroVuoto(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() )
		return ( nodo->getFiglioDestro() == NULL ) ;
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
void Alberobin<T>::insBinRadice()  throw (char const *) {
	if ( binAlberoVuoto() ) {
		posizione nuovaradice = new NodoBin<T>;
		nuovaradice->setPadre( NULL );
		nuovaradice->setFiglioSinistro( NULL );
		nuovaradice->setFiglioDestro( NULL );
		radice = nuovaradice ;
	}
	else
		throw "L'albero non e' vuoto. Impossibile inserire la radice.";
}


template <class T>
void Alberobin<T>::insBinRadice(T value)  throw (char const *) {
	if ( binAlberoVuoto() ) {
		posizione nuovaradice = new NodoBin<T>;
		nuovaradice->setValue( value );
		nuovaradice->setPadre( NULL );
		nuovaradice->setFiglioSinistro( NULL );
		nuovaradice->setFiglioDestro( NULL );
		radice = nuovaradice ;
	}
	else
		throw "L'albero non e' vuoto. Impossibile inserire la radice.";
}

template <class T>
void Alberobin<T>::insBinRadice( Alberobin tree )  throw (char const *) {
	if ( binAlberoVuoto() ) {
		posizione nuovaradice;
		nuovaradice = tree.binRadice();
		radice = nuovaradice ;
	}
	else
		throw "L'albero non e' vuoto. Impossibile inserire la radice.";
}




template <class T>
void Alberobin<T>::insFiglioSinistro(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( sinistroVuoto(nodo) ) {
			posizione nuovonodo = new NodoBin<T>;

			nuovonodo->setPadre( nodo );
			nuovonodo->setFiglioSinistro( NULL );
			nuovonodo->setFiglioDestro( NULL );

			nodo -> setFiglioSinistro( nuovonodo ) ;
		}
		else
			throw "Il figlio sinistro del nodo c'e' gia'";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}


template <class T>
void Alberobin<T>::insFiglioSinistro(posizione nodo, T value)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( sinistroVuoto(nodo) ) {
			posizione nuovonodo = new NodoBin<T>;
			nuovonodo->setValue( value );
			nuovonodo->setPadre( nodo );
			nuovonodo->setFiglioSinistro( NULL );
			nuovonodo->setFiglioDestro( NULL );
			nodo -> setFiglioSinistro( nuovonodo ) ;
		}
		else
			throw "Il figlio sinistro del nodo c'e' gia'";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
void Alberobin<T>::insFiglioSinistro(posizione nodo, Alberobin tree)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( sinistroVuoto(nodo) ) {
			posizione nuovonodo;
			nuovonodo = tree.binRadice();

			nuovonodo -> setPadre(nodo);
			nodo -> setFiglioSinistro( nuovonodo ) ;
		}
		else
			throw "Il figlio sinistro del nodo c'e' gia'";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}






template <class T>
void Alberobin<T>::insFiglioDestro(posizione nodo)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( destroVuoto(nodo) ) {
			posizione nuovonodo = new NodoBin<T>;
			nuovonodo->setPadre( nodo );
			nuovonodo->setFiglioSinistro( NULL );
			nuovonodo->setFiglioDestro( NULL );
			nodo -> setFiglioDestro( nuovonodo ) ;
		}
		else
			throw "Il figlio destro del nodo c'e' gia'";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}





template <class T>
void Alberobin<T>::insFiglioDestro(posizione nodo, T value)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( destroVuoto(nodo) ) {
			posizione nuovonodo = new NodoBin<T>;
			nuovonodo->setValue( value );
			nuovonodo->setPadre( nodo );
			nuovonodo->setFiglioSinistro( NULL );
			nuovonodo->setFiglioDestro( NULL );
			nodo -> setFiglioDestro( nuovonodo ) ;
		}
		else
			throw "Il figlio destro del nodo c'e' gia'";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
void Alberobin<T>::insFiglioDestro(posizione nodo, Alberobin tree)  throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( destroVuoto(nodo) ) {
			posizione nuovonodo;
			nuovonodo = tree.binRadice() ;

			nuovonodo -> setPadre(nodo);
			nodo -> setFiglioDestro( nuovonodo ) ;
		}
		else
			throw "Il figlio destro del nodo c'e' gia'";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}





template <class T>
void Alberobin<T>::cancSottoBinAlbero(posizione nodo)  throw (char const *) {

	if ( !binAlberoVuoto() )

		if ( nodo != NULL ) {
			posizione left = nodo->getFiglioSinistro();
			posizione right = nodo->getFiglioDestro();

			if ( left != NULL )
				cancSottoBinAlbero( left );

			if ( right != NULL )
				cancSottoBinAlbero( right );

			if ( nodo == binRadice() ) {
				radice = NULL;
				delete(nodo);
			} else {
				posizione daddy = nodo->getPadre();

				if ( daddy->getFiglioSinistro() == nodo )
					daddy->setFiglioSinistro(NULL);
				else
					daddy->setFiglioDestro(NULL);

				delete(nodo);
			}
		} else {}
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
T Alberobin<T>::leggiNodo(posizione nodo)  throw (char const *) {
	if ( nodo != NULL )
		return ( nodo->getValue() ) ;
	else
		throw "L'albero è vuoto." ;
}



template <class T>
void Alberobin<T>::scriviNodo(T label, posizione nodo) throw (char const *) {
	if ( nodo != NULL )
		nodo -> setValue(label) ;
	else
		throw "L'albero è vuoto." ;
}



template <class T>
void Alberobin<T>::print() {
	print( binRadice() );
}

template <class T>
void Alberobin<T>::print(posizione nodo) {

	cout << "(" ;

	if ( nodo != NULL ) {
		cout << nodo->getValue() ;

		if ( (nodo->getFiglioSinistro()!=NULL)
			|| (nodo->getFiglioDestro()!=NULL) ) {

			print( nodo->getFiglioSinistro() );
			print( nodo->getFiglioDestro() );
		}

	} else {}

	cout << ")" ;
}



template <class T>
void Alberobin<T>::visitaPreordine() {
	visitaPreordine( binRadice() );
}



template <class T>
void Alberobin<T>::visitaPostordine() {
	visitaPostordine( binRadice() );
}


template <class T>
void Alberobin<T>::visitaSimmetrica() {
	visitaSimmetrica( binRadice() );
}



template <class T>
void Alberobin<T>::visitaPreordine(posizione nodo) {

	if ( !binAlberoVuoto() ) {
		if ( nodo != NULL ) {
				cout << nodo->getValue() << " " ;
				visitaPreordine( nodo->getFiglioSinistro() );
				visitaPreordine( nodo->getFiglioDestro() );
		}
	}
}


template <class T>
void Alberobin<T>::visitaPostordine(posizione nodo) {

	if ( !binAlberoVuoto() ) {
		if ( nodo != NULL ) {
				visitaPostordine( nodo->getFiglioSinistro() );
				visitaPostordine( nodo->getFiglioDestro() );
				cout << nodo->getValue() << " " ;
		}
	}
}


template <class T>
void Alberobin<T>::visitaSimmetrica(posizione nodo) {

	if ( !binAlberoVuoto() ) {
		if ( nodo != NULL ) {
				visitaSimmetrica( nodo->getFiglioSinistro() );
				cout << nodo->getValue() << " " ;
				visitaSimmetrica( nodo->getFiglioDestro() );
		}
	}
}



#endif // _ALBEROBIN_H_
